Deletion problems are those where given a graph $G$ and a graph property$\pi$, the goal is to find a subset of edges such that after its removal thegraph $G$ will satisfy the property $\pi$. Typically, we want to minimize thenumber of elements removed. In fair deletion problems we change the objective:we minimize the maximum number of deletions in a neighborhood of a singlevertex. We study the parameterized complexity of fair deletion problems with respectto the structural parameters of the tree-width, the path-width, the size of aminimum feedback vertex set, the neighborhood diversity, and the size ofminimum vertex cover of graph $G$. We prove the W[1]-hardness of the fair FOvertex-deletion problem with respect to the first three parameters combined.Moreover, we show that there is no algorithm for fair FO vertex-deletionproblem running in time $n^{o(k^{1/3})}$, where $n$ is the size of the graphand $k$ is the sum of the first three mentioned parameters, provided that theExponential Time Hypothesis holds. On the other hand, we provide an FPT algorithm for the fair MSO edge-deletionproblem parameterized by the size of minimum vertex cover and an FPT algorithmfor the fair MSO vertex-deletion problem parameterized by the neighborhooddiversity
展开▼
机译:删除问题是那些给定图形$ G $和图形属性$ \ pi $的问题,目标是找到边的子集,以便在图形被删除后,图形$ G $将满足属性$ \ pi $。通常,我们希望最大程度地减少删除的元素数量。在公平删除问题中,我们更改了目标:我们将单个顶点邻域中的最大删除数量降至最低。我们针对图$ G $的树宽,路径宽度,最小反馈顶点集的大小,邻域分集和最小顶点覆盖的大小的结构参数,研究了公平删除问题的参数化复杂度。相对于前三个参数,我们证明了公平的FOvertex删除问题的W [1]硬度。此外,我们证明了在$ n ^ {o(k ^ {1/3})} $,其中$ n $是图形的大小,$ k $是前面提到的三个参数的总和,前提是要保留指数时间假设。另一方面,我们为通过最小顶点覆盖大小参数化的公平MSO边缘删除问题提供了FPT算法,并为通过邻域多样性参数化的公平MSO顶点删除问题提供了FPT算法。
展开▼